package pers.qianyu.month_202102.date_20210217;

import java.util.*;

/**
 * 887. 鸡蛋掉落
 * https://leetcode-cn.com/problems/super-egg-drop/
 *
 * @author mizzle rain
 * @date 2021-02-17 15:50
 */
public class SuperEggDrop {
    Map<Node, Integer> memo = new HashMap<>();

    public int superEggDrop(int K, int N) {
        return dp(K, N);
    }

    private int dp(int k, int n) {
        if (k == 1) return n;
        if (n == 0) return 0;
        Node node = new Node(k, n);
        if (memo.containsKey(node)) return memo.get(node);
        int left = 1, right = n, res = Integer.MAX_VALUE;
        while (left <= right) {
            int mid = left + right >> 1;
            int a = dp(k - 1, mid - 1), b = dp(k, n - mid);
            if (a > b) {
                right = mid - 1;
                res = Math.min(res, a + 1);
            } else {
                left = mid + 1;
                res = Math.min(res, b + 1);
            }
        }
        memo.put(node, res);
        return res;
    }

    static class Node {
        int k, n;

        public Node(int k, int n) {
            this.k = k;
            this.n = n;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            Node node = (Node) o;

            if (k != node.k) return false;
            return n == node.n;
        }

        @Override
        public int hashCode() {
            int result = k;
            result = 31 * result + n;
            return result;
        }
    }
}
